package com.example.design.leetcode.StackAndQueue;

//剑指 Offer 30. 包含 min 函数的栈

//定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
//
//    示例:
//    MinStack minStack = new MinStack();
//    minStack.push(-2);
//    minStack.push(0);
//    minStack.push(-3);
//    minStack.min();   --> 返回 -3.
//    minStack.pop();
//    minStack.top();      --> 返回 0.
//    minStack.min();   --> 返回 -2.
//
//    提示：
//
//    各函数的调用总次数不超过 20000 次

import java.util.Stack;

// 标签：辅助栈
public class Practice20 {
    Stack<Integer> stack01;
    Stack<Integer> stack02;

    public Practice20() {
        stack01 = new Stack<>();
        stack02 = new Stack<>();
    }

    public void push(int x) {
        stack01.push(x);

        // 辅助栈里的元素是小的在上面，大的在下面
        if (stack02.isEmpty() || stack02.peek() >= x) {
            stack02.push(x);
        }
    }

    public void pop() {
        Integer pop = stack01.pop();
        // 如果栈1pop出去的元素与辅助栈的栈顶元素一致，辅助栈也要pop,保持一致
        if (pop.equals(stack02.peek())) {
            stack02.pop();
        }
    }

    public int top() {
        return stack01.peek();
    }

    public int min() {
        return stack02.peek();
    }
}
